#include <iostream>
#include <string>
#include <vector>
#include <sstream>

using namespace std;

template<class T, class U> T cast(U x)
{
	ostringstream os;
	os << x;
	T res;
	istringstream is(os.str());
	is >> res;
	return res;
}
template<class T> vector<T> split(string s, string x = " ")
{
	vector<T> res;
	for (int i = 0; i < s.size(); i++)
	{
		string a;
		while (i < s.size() && x.find(s[i]) == string::npos)
			a += s[i++];
		if (!a.empty())
			res.push_back(cast<T> (a));
	}
	return res;
}

// Convert Integer to String;
string convertIntegerToString(int number)
{
	stringstream s; //create a stringstream
	s << number; //add number to the stream
	return s.str(); //return a string with the contents of the stream
}
// Convert String to Integer;
int convertStringToInteger(string s)
{
	stringstream ss(s);
	int number;
	ss >> number;
	return number;
}

//Prime factors;

prime_factorization(long x)
{
    long i;         /* counter */
    long c;         /* remaining product to factor */
    c = x;
    while ((c % 2) == 0)
    {
        printf("%ld\n", 2);
        c = c / 2;
    }
    i = 3;
    while (i <= (sqrt(c) + 1))
    {
        if ((c % i) == 0)
        {
            printf("%ld\n", i);
            c = c / i;
        }
        else
            i = i + 2;
    }
    if (c > 1) printf("%ld\n", c);
}

/*
 * // string to int
 * string some_string;
 * istringstream buffer(some_string);
 * int some_int;
 * buffer >> some_int;

 * // int to string
 * int some_int;
 * ostringstream buffer;
 * buffer << some_int;
 * string some_string = buffer.str();
 * */

//Quick-sort:
int Partition(vector<int> &v, int left, int right)
{
	int x = v[left];
	vector<int> less;
	vector<int> great;
	int count = 1;
	for (int i = left; i <= right; i++)
	{
		if (v[i] < x)
			less.push_back(v[i]);
		else if (v[i] > x)
			great.push_back(v[i]);
		else
			count++;
	}
	int idx = left;
	for (int i = 0; i < less.size(); idx++)
	{
		v[idx++] = less[i];
	}
	for (int i = 0; i < count; i++)
	{
		v[idx++] = x;
	}
	int flag = idx;
	for (int i = 0; i < great.size(); i++)
	{
		v[idx++] = great[i];
	}
	return flag;
}
void Quick_Sort(vector<int> &v, int left, int right)
{
	if(left < right)
	{
		int n = Partition(v, left, right);
		Quick_Sort(v, left, n-1);
		Quick_Sort(v, n, right);
	}
}
